package mid.class5;

import common.ArrayUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 图存储结构5
 * 1.有向图
 * 2.无向图
 * *     <- 1 -
 * *   1  - 6 -> 3
 * *   |       / |
 * *   7     5   4
 * *   |   /     |
 * *   v /       |
 * *   2  - 2 -> 4
 * *
 * * 0
 * * 1	[3, 6]	[2, 7]
 * * 2	[4, 2]	[3, 5]
 * * 3	[1, 1]
 * * 4	[3, 4]
 * *
 * <p>
 * <p>
 * 1.邻接矩阵
 * 2.邻接表
 * 3.链式前向星
 */
public class Code01_Graph {
    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {1, 3, 6},
                {4, 3, 4},
                {2, 4, 2},
                {1, 2, 7},
                {2, 3, 5},
                {3, 1, 1}
        };
        int n = 4;

        // 邻接矩阵
        int[][] graph1 = createGraph1(nums, n);
        ArrayUtils.printMatrixArr(graph1);

        // 邻接表
        List<List<int[]>> graph = createGraph2(nums, n);
        printGraph(graph);

    }

    /**
     * 邻接矩阵-创建有向图
     */
    public static int[][] createGraph1(int[][] nums, int n) {
        int[][] graph1 = new int[n + 1][n + 1];
        int[] num = graph1[0];
        for (int i = 0; i < num.length; i++) {
            num[i] = i;
        }

        // 邻接矩阵建图
        for (int[] edge : nums) {
            // 有向图
            graph1[edge[0]][edge[1]] = edge[2];
            // 无向图
//            graph1[edge[0]][edge[1]] = edge[2];
//            graph1[edge[1]][edge[0]] = edge[2];
        }
        return graph1;
    }

    /**
     * 邻接表 - 创建有向图
     */
    public static List<List<int[]>> createGraph2(int[][] nums, int n) {
        List<List<int[]>> graph = new ArrayList<>();

        // 初始化列表
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] num : nums) {
            // 无向图
//            graph.get(num[0]).add(new int[]{1});
            //有向图
            graph.get(num[0]).add(new int[]{num[1], num[2]});
        }
        return graph;
    }


    // 打印试图
    private static void printGraph(List<List<int[]>> graph) {
        int i = 0;
        for (List<int[]> node : graph) {
            System.out.print(i + "\t");
            for (int[] path : node) {
                System.out.print(Arrays.toString(path) + "\t");
            }
            System.out.println();
            i++;
        }
    }

}
